Here are the two parts to recursion:
And here is how this applies to triangle numbers:
The problem "Triangle(N)
" is divided into two
problems: "add N to something"
and "Triangle(N-1)
".
Sometimes the latter can be solved immediately
(when it is the base case). Other times you need to continue breaking the problem into
smaller problems.
Using the above, what is Triangle(4)
?
Fill in the boxes starting with the second column of the top row and work your way down.
When you hit the last row you can work your way up with the last two columns.